'''
匹配子序列，保持相对位置不变
'''


def isSubsequence(s: str, t: str) -> bool:#这样可以告诉别人，参数类型是什么，返回是什么类型
    n, m = len(s), len(t)
    f = [[0] * 26 for _ in range(m)]
    f.append([m] * 26)
    #动态规划
    for i in range(m - 1, -1, -1):
        for j in range(26):
            f[i][j] = i if ord(t[i]) == j + ord('a') else f[i + 1][j]

    add = 0
    for i in range(n):
        if f[add][ord(s[i]) - ord('a')] == m:
            return False
        add = f[add][ord(s[i]) - ord('a')] + 1

    return True

def isSubsequence(self, s: str, t: str) -> bool:
    n, m = len(s), len(t)
    i = j = 0
    while i < n and j < m:
        if s[i] == t[j]:
            i += 1
        j += 1
    return i == n

def isSubsequence(self, s: str, t: str) -> bool:
    if s == "":
        return True
    index = -1
    for i in s:
        index = t.find(i, index+1)
        if index == -1:
            return False
    return True

def isSubsequence(self, s: str, t: str) -> bool:
    if not s:
        return True
    if s[0] in t:
        inx = t.index(s[0])
        return self.isSubsequence(s[1:], t[inx+1:])
    return False

import re

def isSubsequence(self, s: str, t: str) -> bool:
    '''
    s="abc"，而模式串为："[^a]*a[^b]*b[^c]*c"，（意思是“任意个非a，a，任意个非b，b，任意个非c，c”）
    '''
    return None!=re.match(''.join("[^%s]*%s"%(ch,ch) for ch in s),t)

if __name__ == '__main__':
    s = "abc"
    t = "ahbgdc"
    print(isSubsequence(s, t))